1. Technical Field
This disclosure relates generally to memory management in a data processing system and more specifically to single pass marking of finalizable objects in the data processing system.
2. Description of the Related Art
In a Java® virtual machine (Lindholm and Yellin, “The Java Virtual Machine Specification, 2ed”, 1999; Java is a registered trademark of Oracle and/or its affiliates), and in other managed runtimes such as VisualAge® for Smalltalk from IBM® and the .NET framework from Microsoft® (IBM and VisualAge are registered trademarks of IBM in the United States and/or other countries; Microsoft is a registered trademark of Microsoft Corporation in the United States and/or other countries), unreachable objects are reclaimed by a garbage collector. Many languages using garbage collection as a part of memory management, such as Java, Smalltalk and C#, provide support for ‘finalizable’ objects.
In the Java language a finalizer is process, which performs finalization tasks for an object in contrast with a constructor, which creates and initializes an instance of a Java class. The finalizer is optionally used to perform a cleanup on an instance of the class and to release resources, including file descriptors, previously held by the object when the object is no longer needed. The resources are released for subsequent use by other objects. Instances of classes that implement a finalize method are often called finalizable objects.
When a Java object is no longer needed, the garbage collector in Java typically recycles memory allocated to the object automatically for use by other objects. However when an instance of a class implements a finalize method, the allocated memory is not recycled by the garbage collector immediately because the object is appended to a special queue for the finalization process. After successful completion of the finalization process the object is ready for a next iteration of garbage collection, therefore typically two or more garbage collection cycles are needed to reclaim resources previously held by a finalizable object.
The garbage collector is required to detect when the finalizable objects become unreachable and enqueue the objects for special processing invoking an associated finalize method for the objects. The memory allocated to these objects may not be reclaimed until processing has completed and the object once again becomes unreachable.
Even though the collector has determined finalizable objects are unreachable, the collector must keep the objects alive, along with the closure of objects reachable from the finalizable objects. An introduction to finalization and finalizable-reachable objects (in C#) is provided in an article entitled “Garbage Collection: Automatic Memory Management in the Microsoft .NET Framework, ” by Jeffrey Richter.
In typical garbage collector implementations, the garbage collector traces all strong roots (for example, system classes, thread stack frames . . . ) and follows all objects directly or indirectly reachable from the traced roots. The garbage collector may mark the objects in a mark map or use another mechanism to indicate an object is strongly reachable. The marking may be done in parallel and/or concurrently.
When all strongly reachable objects have been discovered, the collector processes finalizable objects. The collector walks through a list of finalizable objects. For each finalizable object, the collector determines whether the object has been marked as strongly reachable. When the object has not been marked as strongly reachable, the collector enqueues the object for finalization and marks the object as reachable. When this operation is completed, the collector follows all objects directly or indirectly reachable from the finalizable objects, marking the objects as reachable.
In worst-case scenarios, finalizable objects may retain large graphs of objects, requiring significant time to trace. Tracing of large graphs of objects introduces delays into a portion of the garbage collector which is typically not concurrent or incremental, and may not even be processed in parallel in some implementations.
While a number of known solutions to this problem are available, none are entirely satisfactory. Final tracing of finalizable-reachable objects may be parallelized to take advantage of multiple processing resources (cores) in the machine, for example the Java virtual machine available from IBM uses this solution. In general this technique works, but there may be insufficient workload to fully benefit from parallelization. For example, only a number of the processors may be fully utilized while other processors remain idle.
Final tracing of finalizable-reachable objects may be incrementalized. By breaking the final processing into multiple steps the collector can set a bound for the maximum pause times. However, incrementalizing this step can be difficult, requiring either a snapshot-at-the-beginning write barrier or additional card cleaning phases. The additional operations can increase the overall garbage collection time, although the technique does reduce the maximum pause time. Final tracing of finalizable-reachable objects may also be made concurrent in another variation. The concurrent variation has the same problems as the incremental solution.
A number of solutions have been proposed to reclaim finalizable-reachable objects more quickly, for example Memory Management Method and System by Hiroshi Inoue, and Methods, Apparatus, and Program Products for Improved Finalization by Antonios Printezis and Peter B. Kessler. However the proposed solutions typically do not address the problem of tracing finalizable-reachable objects efficiently. The problem just described can typically be generalized to other types of weakly reachable objects, specifically, in Java; the problem also applies to phantom-reachable objects.
In other previous examples, a technique is described to improve concurrent sweeping when mark bits are stored directly in an object header. In another example, a mechanism is described for detecting popular objects, which may have incoming references. A previous technique describes a distributed garbage collector in which each node uses a work stack and mark map thereby segregating the objects by respective locations. When the collection operation is completed the mark maps are merged.
In yet another example, a garbage collector is described that selects untraced objects, as speculative roots presuming the object might be reachable. When the object is reachable, the speculative mark map is merged with an actual mark map. There is therefore a need for a more efficient garbage collector.